package problem712;

//712.两个字符串的最小ascii删除和
//https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        s1 = " " + s1;
        s2 = " " + s2;
        int sum = 0;
        int[][] dp = new int[n+1][m+1];
        for(int i = 1; i<=n; i++) {
            sum += s1.charAt(i);
        }
        for(int j = 1; j<=m; j++) {
            sum += s2.charAt(j);
        }
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                if(s1.charAt(i) == s2.charAt(j)) dp[i][j] = dp[i-1][j-1] + s1.charAt(i);
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        System.out.println(sum + " " + dp[n][m]);
        return sum - 2*dp[n][m];
    }
}

/*

dp[i][j]:s1的[0,i]区间以及s2的[0,j]区间内的所有子序列里
         公共子序列的 ascii 最大和

*/